package offer;

/**
 * @author ZhanBo
 * @date 2020/6/21
 */
public class Solution36 {


    /**
     * 剑指 Offer 36. 二叉搜索树与双向链表
     * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
     * 为了让您更好地理解问题，以下面的二叉搜索树为例：
     *
     * @param root
     * @return
     */
    public Node treeToDoublyList(Node root) {
        if(root == null) {
            return null;
        }
        dfs(root);
        //链表的头节点的前驱指向最后一个节点
        head.left = pre;
        //链表的尾节点的后继指向第一个节点
        pre.right = head;
        return head;
    }

    public Node pre, head;

    /**
     * 中序遍历
     * @param cur
     */
    public void dfs(Node cur) {
        if(cur == null) {
            return;
        }
        dfs(cur.left);
        //如果前驱不为空，说明是第一个节点
        if(pre != null) {
            //让前驱的后继指向当前节点
            pre.right = cur;
        } else {
            //第一个节点为头节点
            head = cur;
        }
        //当前节点的左指针指向前驱节点
        cur.left = pre;
        //前驱移动到当前节点
        pre = cur;
        dfs(cur.right);
    }

    public static void main(String[] args) {

    }

}
